import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-11-15
 * Time: 22:46
 */
public class Solution {

    /**
     *  BFS
     */
    public int numWays1(int n, int[][] relation, int k) {
        List<Integer>[] lists = new List[n];
        int len = relation.length;
        for (int i = 0; i < n; i++) {
            lists[i] = new ArrayList<>();
        }
        for (int i = 0; i < len; i++) {
            int from = relation[i][0];
            int to = relation[i][1];
            lists[from].add(to);
        }
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(0);
        while (!queue.isEmpty() && k > 0) {
            k--;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int from = queue.poll();
                for (Integer x: lists[from]) {
                    queue.offer(x);
                }
            }
        }
        int count = 0;

        for (Integer x: queue) {
            if (x == n-1) {
                count++;
            }
        }
        return count;
    }


    /**
     动态规划
     dp[i][j] 表示 走 i 步到达 j 的方法数
     dp[i][j] = sum(dp[i-1][from]) 其中 to = j
     */
    public int numWays2(int n, int[][] relation, int k) {
        int[][] dp = new int[k+1][n];
        dp[0][0] = 1;
        for (int i = 1; i <= k; i++) {
            for (int j = 0; j < n; j++) {
                for (int[] arr: relation) {
                    int from = arr[0];
                    int to = arr[1];
                    if (to == j) {
                        dp[i][j] += dp[i-1][from];
                    }
                }
            }
        }
        return dp[k][n-1];
    }


    /**
     *  动态规划优化
     *  ① 是 最外层只需要一层循环
     *  ② 是 使用一维数组
     *  如何解决更新覆盖问题 ?
     *  用 dp 记录已经更新过的数组
     *  用 next 记录当前需要记录的数组
     *  然后 把 next 赋值给 dp
     */
    public int numWays3(int n, int[][] relation, int k) {
        int[] dp = new int[n];
        dp[0] = 1;
        for (int i = 1; i <= k; i++) {
            int[] next = new int[n];
            for (int[] arr: relation) {
                int from = arr[0];
                int to = arr[1];
                next[to] += dp[from];
            }
            dp = next;
        }
        return dp[n-1];
    }
}
